#include <iostream>  
#include <vector>  
#include <cstdlib>  
#include <ctime>  
#include <algorithm>  
  
using namespace std;  
  
// 填充数组  
void fillRandomArray(vector<int>& arr, int seed) {  
    srand(seed);  
    for (int i = 0; i < arr.size(); ++i) {  
        arr[i] = rand();  
    }  
    sort(arr.begin(), arr.end()); // 排序  
}  
  
// 查找第k小的数  
int findKth(const vector<int>& nums1, int start1, const vector<int>& nums2, int start2, int k) {  
    // 边界情况  
    if (start1 >= nums1.size()) return nums2[start2 + k - 1];  
    if (start2 >= nums2.size()) return nums1[start1 + k - 1];  
    if (k == 1) return min(nums1[start1], nums2[start2]);  
  
    // 排除部分元素  
    int half = k / 2;  
    int end1 = min(start1 + half, (int)nums1.size());  
    int end2 = min(start2 + half, (int)nums2.size());  
      
    if (nums1[end1 - 1] < nums2[end2 - 1]) {  
        return findKth(nums1, start1 + half, nums2, start2, k - half);  
    } else if (nums1[end1 - 1] > nums2[end2 - 1]) {  
        return findKth(nums1, start1, nums2, start2 + half, k - half);  
    } else {  
        // 当两个数组中的第k/2小的数相等时，任意一个都可以作为第k小的数  
        // 但为了保持算法的一致性，我们可以选择继续搜索后半部分  
        return findKth(nums1, start1 + half, nums2, start2 + half, k - half);  
    }  
}  
  
// 查找中位数  
double findMedianSortedArrays(const vector<int>& nums1, const vector<int>& nums2) {  
    int total = nums1.size() + nums2.size();  
    if (total % 2 == 1) {  
        // 总数是奇数，直接找中间那个数  
        return findKth(nums1, 0, nums2, 0, total / 2 + 1);  
    } else {  
        // 总数是偶数，找中间两个数的平均值  
        int mid1 = findKth(nums1, 0, nums2, 0, total / 2);  
        int mid2 = findKth(nums1, 0, nums2, 0, total / 2 + 1);  
        return (mid1 + mid2) / 2.0;  
    }  
}  
  
int main() {  
    int n = 10; // 假设数组长度为10  
    int seed1, seed2;  
    cout << "Enter your student ID for seed: ";  
    cin >> seed1;  
    seed2=seed1;
      
    vector<int> X(n), Y(n);  
    fillRandomArray(X, seed1);  
    fillRandomArray(Y, seed2 / 2); // 使用学号除以2作为第二个数组的种子  
      
    double median = findMedianSortedArrays(X, Y);  
    cout << "The median of the combined arrays is: " << median << endl;  
      
     
    return 0;  
}